package com.xyj.week04;

import java.util.HashMap;
import java.util.Map;

/**
 * @author GuXiaoYao
 * @version 1.0.0
 * @since 2021/9/6
 */
public class T2 {

    public static void main(String[] args) {
        System.out.println(checkInclusion("abcdxabcde", "abcdeabcdx"));
    }

    public static boolean checkInclusion(String s1, String s2) {

        char [] c1s= s1.toCharArray();
        // 维护两个Map，一个Map用来存放有效的字符，
        // 另一个用来存放窗口内的字符
        Map<Character,Integer> availableMap =new HashMap<>(c1s.length);
        Map<Character,Integer> windowMap =new HashMap<>();
        // 遍历将字符放入map中
        for(char c:c1s) {
            availableMap.put(c,availableMap.getOrDefault(c,0)+1);
        }
        // s2对应的char数组
        char [] c2s=s2.toCharArray();
        int right=0,flag=0,left=0;

        while(right<s2.length()){
            char cur=c2s[right];
            // 右边窗口一直跑
            right++;
            // 判断当前字符是否是有效值
            if( availableMap.containsKey(cur) ){
                windowMap.put(cur,windowMap.getOrDefault(cur,0)+1);
                // 判断当前字符出现次数是否和有效次数一致
                if( windowMap.get(cur).equals(availableMap.get(cur)) ){
                    //如果一致的话，flag+1
                    flag++;
                }
            }
            // 如果窗口每次到达 s1.length()的长度
            if (right- left==s1.length()) {
                // 判断当前的有效值是不是等于s1的长度
                if (flag==availableMap.size()){
                    return true;
                }
                // 获取即将移除窗口的值
                char willRemove=c2s[left];
                left++;
                if (availableMap.containsKey(willRemove)){
                    //如果是有效的 判断是不是有效值和window中相同  如果相同，说明flag --
                    if (availableMap.get(willRemove).equals(windowMap.get(willRemove))) {
                        //注意这里要先判断再移除元素 。（注意理解）
                        flag--;
                    }
                    windowMap.put(willRemove,windowMap.getOrDefault(willRemove,0)-1);
                }
            }
        }
        return false;

    }
}
